Questionable LeetCode

Friend has been on the job hunt and mentioned using LeetCode to prep for his interviews – I got curious and checked it out. It’s a pretty cool site where you can solve coding problems and compare your solutions with others. It also made me feel a little nuts.

What I saw on LeetCode #

In LeetCode’s onboarding, they suggest solving a very simple problem to learn how the platform works:

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

…

Example 3:

Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]

Simple enough. I’d usually do something simple like this:

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        result = []
        total = 0
        for num in nums:
            total += num
            result.append(total)

        return result

And here were the results:

Ok, so I’m good on memory usage but quite slow compared to other solutions. I browse some of the other solutions, some advertising being very fast, but none of them stand out as being obviously faster. Sure enough, when I run their solutions I get roughly the same results. I get curious and just rerun my solution a couple times.

Well that’s interesting – the same code is rated as slower than 85% of solutions in one run and faster than 50% in another. And somehow the memory usage is different too? So these metrics aren’t very useful – at least not for very simple algorithms.

The only shared solution I found that looked like it could actually be faster used a built in method accumulate() – I figured it would use C behind the scenes to beat raw python.

Still, I was surprised my simple solution wasn’t what others were sharing. I would click on solutions labeled stuff like “easy peasy” and see this:

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        List = []
        for i in range(len(nums)):
            if(i == 0):
                List.append(nums[0])
            else:
                List.append(nums[i] + List[i-1])
        return List

Not what I would call easy or peasy!

• They named their variable List which is not pythonic snake_case and collides with python’s own typing.List
• They use range() – which is uneccessary clutter – but if you’re using it, it can be supplied a starting index. Doing so would let them simply assign [0] and remove the if/else happening every iteration.
• And this is a nitpick, but I think it’d be more readable to have nums[i] on the right side of the addition equation (you’re adding the latest value to the running sum)

“Optimizations” #

Most of the other solutions seemed to follow a few common “optimizations” that I was skeptical of – they made the code less readable and I wanted to actually profile them to see if there really were gains to be had in exchange. As a baseline, here’s how my solution and accumulate() performed (ten thousand iterations on a nums list with 2000 numbers):

runningSum (10000 on 2000) duration = 0.7427482604980469
runningSumAccumulate (10000 on 2000) duration = 0.4288499355316162

As you can see, contrary to LeetCode’s profiling tools, accumulate() really does provide a significant boost to speed. Unless I really needed the performance, I’d probably still go with my solution because nobody has to look up what accumulate() does when reading my code – and if I did use it, I’d link to the documentation. Anyway, here are some common things I saw people doing instead:

Removing the “total” variable #

def runningSumLookback(self, nums: List[int]) -> List[int]:
    result: List[int] = [nums[0]]
    for i in range(1, len(nums)):
        result.append(result[i - 1] + nums[i])

    return result

Yes, you can just look at the previous number to calculate the next sum instead of keeping a running total in its own variable. Sacrifice a little readability for better performance? Nah, it’s almost twice as slow:

runningSumLookback (10000 on 2000) duration = 1.3393068313598633

Preallocating your list because you think .append() is slow #

def runningSumPrealloc(self, nums: List[int]) -> List[int]:
    result: List[int] = [None] * len(nums)
    total: int = 0
    for i, num in enumerate(nums):
        total += num
        result[i] = total

    return result

I get why someone would think this would help. Other languages often don’t like to change the size of their arrays when it can be avoided. But it seems to have the opposite effect in python:

runningSumPrealloc (10000 on 2000) duration = 1.0288589000701904

You can improve performance a bit (still slower than my solutions at the top) by using range() instead of enumerate() but it’s not much and enumerate() is cleaner.

One liner using list comprehension #

def runningSumOneLiner(self, nums: List[int]) -> List[int]:
    return [sum(nums[:i + 1]) for i in range(len(nums))]

I guess there’s some intuition that shorter code = faster code, but in this case it’s over 100X slower:

runningSumOneLiner (10000 on 2000) duration = 104.43448996543884

And you’ve sacrificed a lot of readability, for everyone that isn’t super familiar with list comprehension, to get that performance degredation.

“Optimizing” your code by reusing the input list #

def runningSumInPlace(self, nums: List[int]) -> List[int]:
    for i in range(1, len(nums)):
        nums[i] = nums[i - 1] + nums[i]
    return nums

I saw solutions like this get a lot of praise on LeetCode. The biggest problem with this is that you’re modifying your input and still returning a now redundant output.

input = [1,4,8,3,4]
print(f"{input = }")
output = sol.runningSumInPlace(input)
print(f"{input = }")
print(f"{output = }")

will print

input = [1, 4, 8, 3, 4]
input = [1, 5, 13, 16, 20] # uh oh
output = [1, 5, 13, 16, 20]

This will increase the likelihood of bugs because you’re changing the input list when people would probably not expect you to. And what do you get in return for making your code more dangerous? Slower code! 🎉

runningSumInPlace (10000 on 2000) duration = 4.2900190353393555

Performance Comparison #

runningSum (10000 on 2000) duration = 0.7427482604980469
runningSumAccumulate (10000 on 2000) duration = 0.4288499355316162
runningSumLookback (10000 on 2000) duration = 1.3393068313598633
runningSumPrealloc (10000 on 2000) duration = 1.0288589000701904
runningSumOneLiner (10000 on 2000) duration = 104.43448996543884
runningSumInPlace (10000 on 2000) duration = 4.2900190353393555

TLDR #

Do not try to get fancy with your code at the expense of readability… especially if you’re also making your code run considerably slower! Sometimes the simpler, more readable code is also faster. If you’re taking simple code and trying to optimize it to run faster, actually test how much you’re optimizing.

Final Note #

And to be clear, this could very well not be representative of LeetCode’s community – this is a very simple problem after all, so maybe the more experienced coders just skip over it. I could imagine the harder problems would have more insightful answers. And presumably the small discrepencies in runtime/memory usage would be negligible with more complex tasks that take more resources to complete. This wasn’t meant to be a critique of LeetCode – LeetCode just happened to offer a great example of a pet peeve of mine in the world of programming.

And I consider myself an alright programmer but by no means am I a programming god – if I’m off base with any of this please do comment and enlighten me.

Full snippet if you want to test yourself #

import time
from typing import List
from itertools import accumulate

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        result: List[int] = []
        total: int = 0
        for num in nums:
            total += num
            result.append(total)

        return result

    def runningSumAccumulate(self, nums: List[int]) -> List[int]:
        return list( accumulate(nums) )

    def runningSumLookback(self, nums: List[int]) -> List[int]:
        result: List[int] = [nums[0]]
        for i in range(1, len(nums)):
            result.append(result[i - 1] + nums[i])

        return result

    def runningSumPrealloc(self, nums: List[int]) -> List[int]:
        result: List[int] = [None] * len(nums)
        total: int = 0
        for i, num in enumerate(nums):
            total += num
            result[i] = total

        return result

    def runningSumPreallocRange(self, nums: List[int]) -> List[int]:
        result: List[int] = [None] * len(nums)
        total: int = 0
        for i in range(len(nums)):
            total += nums[i]
            result[i] = total

        return result

    def runningSumOneLiner(self, nums: List[int]) -> List[int]:
        return [sum(nums[:i + 1]) for i in range(len(nums))]

    def runningSumInPlace(self, nums: List[int]) -> List[int]:
        for i in range(1, len(nums)):
            nums[i] = nums[i - 1] + nums[i]
        return nums

    def run(self, method, iterations: int = 10000):
        start_time = time.time()
        input = [7, 5, 9, 8, 1, 3] # my tests ran with 2000 numbers in this list
        for i in range(iterations):
            method(input)

        duration = time.time() - start_time
        print(f"{method.__name__} ({iterations} on {len(input)}) {duration = }")


sol = Solution()

sol.run(sol.runningSum)
sol.run(sol.runningSumAccumulate)
sol.run(sol.runningSumLookback)
sol.run(sol.runningSumPrealloc)
sol.run(sol.runningSumPreallocRange)
sol.run(sol.runningSumInPlace)
sol.run(sol.runningSumOneLiner)

input = [1,4,8,3,4]
print(f"{input = }")
output = sol.runningSumInPlace(input)
print(f"{input = }")
print(f"{output = }")